Computation, whether understood as explicit executions on hardware or more abstractly as literal sequences of otherwise unspecified events, is inherently time-like, in that at its very core, each step is fundamentally irreversible. Sequential computation by its very nature consumes information, and this includes so-called parallel processing, or parallelism—the organized execution of multiple copies of one or more sequential processes. These are facts supported by key mathematical theorems by Alan Turing (1920-40's) and Claude Shannon (1948++).
The present disclosure presents a new kind of computation—Space-like Computation—that is the conceptual opposite of time-like computation. Space-like computation is reversible (i.e., wave-like) and creates information. Space-like computations rest on novel mathematics, which show that space-like computations are in principle different from traditional sequential (and parallel) computations.
As a result, there is no inbuilt sense of “time” in a space-like computation, although there is plenty of change. This change can either be viewed as the evolution of a complex waveform (representing the activity spectrum of the computation) or as the dynamics of a population of discrete concurrent bit-flips—the two views are EXACTLY equivalent, courtesy of another theorem, Parseval's Identity (1799), and are explained further below.
Parseval's Identity states that the projection of a function F onto an n-dimensional orthogonal space is the Fourier decomposition of F. Parseval's Identity is a generalization of the Pythagorean theorem to n dimensions. In the n-dimensional coordinate system, F's current value corresponds to a hyper-hypotenuse in an n-dimensional hyper-cube, and the projection breaks that hyper-hypotenuse down into the various pieces along each of the dimensions that go into its construction.
To construct an n-dimensional volume, begin with an ordinary plane right triangle with unit sides a and b. Reflect this triangle on its hypotenuse, forming a rectangle with sides a and b, area ab, and diagonal d=sqrt(a2+b2). Next, lift this rectangle vertically (length c) to make a three-dimensional (3D) volume abc. Its diagonal is d=sqrt(a2+b2+c2) and this sum-of-squares symmetry continues as we make a 4D volume, then 5D, etc.
At the same time, going back to the starting right triangle, we can also express the sides a and b as a=d cos θ and b=d sin θ, where θ is the angle between a and the hypotenuse. Substituting these sine and cosine equivalents for a, b, c, . . . up through the dimensions will yield, for the n-dimensional hypotenuse (which is the current value of the function F, whose projection we began with), a sum of sines and cosines, i.e., Fourier's world.
So the world of waves and the world of orthogonal coordinate systems are the same world. It is in the latter that we will connect to computation. The connection is this: let each dimension correspond to the state of some process, where all these processes a, b, c, . . . , ab, ac, . . . , abc, . . . are notionally independent (i.e., orthogonal), though interacting otherwise freely and concurrently. Further, let each of these processes a, b, c, . . . , ab, ac, . . . , abc, . . . be in one of two possible states at any particular time.1 An analysis of the process-state evolution in such a system reflects that some or all of the processes change their state at some frequency, with the processes that are interactions (i.e., m-vectors) changing at a lower frequency than their constituent processes. The processes can be seen to separate into frequency bands according to the number of bits of state (i.e., m): the high frequency bands contain the more frequently-changing individual, one-dimensional processes a, b, c, . . . , revealing short-term, high-resolution data about the system; low frequency bands correspond to long-term symmetries and global developments, represented by processes of increasing dimensions (e.g., ab, abc, abcd, etc.). In the geometric (Clifford) algebra over Z3={0, 1, −1} used here, 1-vectors are processes with one bit of state, ±1, and an m-vector thus has m bits of state. For concurrent processes a, b, we write a+b; when a, b interact we write ab. ab too is a process with two bits of state and an external appearance±1.
Via Parseval's Identity, the frequency bands correspond to expressions in the algebra, which in turn correspond to collections of interactions. The Fourier decomposition of this system can be said to perform cross-summation of these frequency bands. The relationship of these cross-summed Fourier bands to the frequencies of change of the individual processes in the system can be analogized to the relationship between qualia—the feeling or experience of a sensation—and perception (e.g., the sum of all experiences of redness vs. the optical light frequencies detected by individual retinal cells).
A space-like computation S is characterized by the following six properties.
First, a space-like computation is distributed, which means that the entire system, consisting of a potentially very large number of concurrent, independent but interacting entities comprised of one or more processes, exhibits coherent global behavior with little or no centralized control. The exact technological criteria for how to design and build distributed systems in general have proven elusive, which lacuna the present invention fills.
Second, a space-like computation is self-organizing, meaning that given some method and the necessary inputs from a surrounding environment that includes the space-like computation (herein, the “surround”), the components of the space-like computation will—over time—assemble these inputs into a coherent entity of discrete units (i.e., other entities, individual processes, or a combination thereof) that interacts with that surround in a stable fashion to accomplish the method. How to design self-organizing computations is a current topic of high-profile research, which the present invention advances.
Third, a space-like computation is hierarchical, meaning that the self-organization includes the creation of new discrete units that represent combinations of the initial units—and combinations of those combinations, and so on—which new units are then subjected to the self-organizational method. Hierarchy is a universal and well-proven technological tool to control conceptual complexity, a tool whose use is found across the industry, from programming languages to databases to communication protocols.
Fourth, a space-like computation is not Turing-limited, meaning that a true space-like computation cannot be simulated by a universal Turing machine, which is by definition limited to sequential computations (including parallelism). This is the topic of the Coin Demonstration (below), which gives an easily understood counter-example. It is widely thought that Turing's theorems prove that all computation is sequential in principle, thus the present disclosure contradicts established norms.
Fifth, a space-like computation is meaningless unless connected to, and interacting with, a surround, because if it is unconnected it cannot grow. As opposed, say, to a sequential computation that computes the value of π, which computation presumably would find genuine meaning in its solitary endeavor, its world being complete.
Sixth, a space-like computation uses a broadcast/listen communications discipline. That is, the space-like computation broadcasts its own state and listens (i.e., reacts) accordingly to other broadcasted states. The reason for this is that the alternative, a request/reply discipline, is inherently functional in character, since it implements y=f(x): “Request that f do its thing on x and reply with the result.” But one man's y is another man's x, so z=g(y) is also a possibility. But then g(y)=g(f(x)), and the requirement first-do-f-then-do-g in order to obtain z is inherently sequential and time-like. This is how contemporary computer systems are organized. In contrast, a space-like computation assembles the steps in its sequential processes on-the-fly, as described further below. Contemporary technology largely ignores broadcast/listen protocols because they do not fit the dominant y=f(x) (i.e., sequential) organizational paradigm.
The following Coin Demonstration clarifies the fundamental reasoning underlying these concepts:
Act I. A man stands in front of you with both hands behind his back. He shows you one hand containing a coin, and then returns the hand and the coin behind his back. After a brief pause, he again shows you the same hand with what appears to be an identical coin. He again hides it, and then asks, “How many coins do I have?”
The best answer at this point is that the man has “at least one coin”, which implicitly seeks one bit of information, and two possible but mutually exclusive states: state1=“one coin,” and state2=“more than one coin.”
One is now at a decision point—if one coin then do X else do Y—and exactly one bit of information can resolve the situation. Said differently, when one is able to make this decision, one has ipso facto received one bit of information.
Act II. The man now extends his hand and it contains two identical coins.
Stipulating that the two coins are in every relevant respect identical to the coins we saw earlier, we now know that there are two coins, that is, we have received one bit of information, in that the ambiguity is resolved. We have now arrived at the demonstration's dramatic peak:
Act III. The man asks, “Where did that bit of information come from?”
The bit originates in the simultaneous presence of the two coins—their co-occurrence—and encodes the now-observed fact that the two processes, whose states are each one of the coins, do not exclude each other's existence when in said states. Furthermore, the states are simultaneous and independent, and therefore indistinguishable in terms of time (i.e., sequence).
Thus, there is information in (and about) the environment that cannot be acquired sequentially, and true concurrency therefore cannot be simulated by a Turing machine. Can a given state of process a exist simultaneously with a given state of process b, or do they exclude each other's existence? This is the fundamental distinction.
More formally, we can by definition write a+a′=0 and b+b′=0 (′=not=minus), meaning that (process state) a excludes (process state) a′, and (process state) b excludes (process state) b′. Their concurrent existence can be captured by adding these two equations, and associativity gives two ways to view the result. The first is:(a+b′)+(a′+b)=0which is the usual excluded middle: if it's not the one, then it's the other. This arrangement is convenient to our usual way of thinking, and easily encodes the traditional one/zero (or 1/1′) distinction. The second view is:(a+b)+(a′+b′)=0which are the two superposition states: either both, or neither. That said, technically there are no superpositions of a/a′ and b/b′ as one-dimensional processes; rather, they are exclusionary distinctions. Superposition first emerges at the second level of processes (i.e., ab) via the distinction exclude vs. co-occur.
The Coin Demonstration shows that by its very existence, a 2-co-occurrence like a+b contains one bit of information. Co-occurrence relationships are structural, or space-like, by their very nature. This space-like information (as opposed to time-like information) ultimately forms the structure and content of the Fourier bands (e.g., all 2-vectors). As described above, sets of m-vectors—{xy}, {xyz}, {wxyz}, . . . —are successively lower undertones of the concurrent flux at the system boundary x+y+z+ . . . , and constitute a simultaneous structural and functional decomposition of that flux into a hierarchy of stable and meta-stable processes. The lower the frequency, the longer-term its influence.
But where do these m-vectors come from?
Act IV. The man holds both hands out in front of him. One hand is empty, but there is a coin in the other He closes his hands and puts them behind his back. Then he holds them out again, and we see that the coin has changed hands. He asks, “Did anything happen?”
To the above two concurrent exclusionary processes a, b we now apply the co-exclusion inference, whose opening syllogism is: if a excludes a′, and b excludes b′, then (a+b′) excludes (a′+b) (or, conjugately, a+b excludes a′+b′). The co-exclusion inference's conclusion is: therefore, ab exists. The reasoning is that we can logically replace the two one-bit-of-state processes a, b with one two-bits-of-state process ab, since what counts in processes is sequentiality, not state size, and exclusion births sequence (here, in the form of alternation between the two complementary states). That is, the existence of the two co-exclusions (a+b′)|(a′+b) and (a+b)|(a′+b′) contains sufficient information for ab to be able to encode them, and therefore, logically and computationally speaking, ab can rightfully be instantiated.
We write δ(a+b′)=ab=−δ(a′+b) and δ(a+b)=ab=−δ(a′+b′), where δ is a co-boundary operator (analogous to integration in calculus). Differentiation is the opposite: δ(ab)=a+b. A fully realized ab is, we see, comprised of two conjugate co-exclusions, a sine/cosine-type relationship. Higher grade operators abc, abcd, . . . are constructed similarly: δ(ab+c)=abc, δ(ab+cd)=abcd, etc. This is the core of the present self-organization method.
We can now answer the man's question, Did anything happen? We can answer, “Yes, when the coin changed hands, the state of the system rotated 180 degrees: ab(a+b′)ba=a′+b.” We see that one bit of information (“something happened”) results from the alternation of the two mutually exclusive states. The transition δ(a+b)=ab is in fact the basic act of perception, called the first perception, subsequent meta-perceptions being derivative.
The presently described systems and methods implement space-like computations on computing devices, in which the processes of the computations carrying the above-described semantics, because the processes are based on co-exclusion.